In a machine-to-machine (M2M) network, devices such as sensors and smart meters measure data, such as temperatures, energy consumptions, machine operations, vehicle telematics, etc. Measured data are communicated through the network (wireless, wired or hybrid) to applications that process the data. Standards Development Organizations (SDOs), such as the Association of Radio Industries and Businesses (ARIB), the Telecommunication Technology Committee (TTC) of Japan, the Alliance for Telecommunications Industry Solutions (ATIS), the Telecommunications Industry Association (TIA) of the USA, the China Communications Standards Association (CCSA), the European Telecommunications Standards Institute (ETSI), the Telecommunications Technology Association (TTA) of Korea, and the Global Standards Collaboration (GSC) seek to develop end-to-end specifications for M2M communications using common use cases and architecture principles across multiple M2M applications.
The wireless M2M network is similar as conventional sensor network or ad hoc network in the sense of network topology and multi-hop communication. Devices in a wireless M2M network can form mesh networks, a star networks, or both. Data measured by the devices can be relayed multiple hops to a gateway or data concentrator.
However, the M2M network is different from conventional networks in that devices in a M2M network are typically heterogeneous. Some devices such as personal computers have sufficient resources, such as memory, processing power, power supply, etc. On the other hand, small devices such as temperature sensors have very limited resources. These resource constrained devices are not capable of communicating large volumes of data, such as audio-visual data. In conventional sensor network or ad hoc network, all devices tend to be homogeneous with the same capability and resources. Typically, sensor devices only transmit limited amounts of data, which allows peer devices to queue and forward data towards the gateway or data concentrator. Therefore, clustering devices in a M2M network is different from clustering devices in conventional sensor network.
There are existing cluster methods for conventional sensor networks and ad hoc networks. For example, an application-specific architecture for wireless micro-sensor networks, called low-energy adaptive clustering hierarchy (LEACH), selects a cluster head in a deterministic way. LEACH protocol shares the cluster head role among all devices in the network. In each transmission round, a fixed percentage of the devices are selected as cluster heads. Within a cluster, cluster members communicate their data to the cluster head using time-division multiple access (TDMA), which allows the devices to be in standby mode when not transmitting data. However, LEACH is not suitable for M2M networks that use heterogeneous M2M devices, particularly resource constrained devices.
U.S. Pat. No. 8,055,740 describes a method for managing clusters in a wireless sensor network. A cluster head collects sensing data from sensor nodes and aggregates the sensing data. The cluster head of master cluster transmits aggregated data to a sink node, and a cluster head of slave cluster transmits aggregated data to the master cluster. If the cluster size of the master cluster is less than a threshold, then the cluster head of this master cluster merges this cluster into another master cluster as a slave cluster. If the cluster size of the master cluster is greater than a threshold, then cluster head of the slave cluster splits its cluster from the master cluster. This method includes heavy overhead by transmitting periodic discovery packets to determine link stability values, cluster size requests, and response packets. It does not consider collision reduction.
U.S. Pat. No. 7,961,673 describes a method for clustering devices in a wireless network. That network includes an access point and multiple computing units grouped into a cluster as a function of a predetermined parameter. The cluster includes a cluster head and at least one cluster member. The cluster member uses a first power level when communicating with the cluster head, and the cluster head unit uses a second power level when communicating with the access point. That method assumes location information is available. In a M2M network, obtaining locations for all devices is not feasible. Another limitation of that method assumes the devices are capable of multi-power level transmission.
U.S. Pat. No. 7,590,611 describes a clustering method for a wireless sensor network that minimizes energy consumption. That method determines a number of initial nodes within transmission range of an ordinary node, which is within a transmission range of a cluster head, and setting an ordinary node having a highest number of initial nodes, as a gateway. A cluster head collect and aggregate data, and a gateway routes aggregated to a data sink. The method tries to minimize the number of cluster heads and gateways because they consume more energy than ordinary nodes. One disadvantage of that method is communication overhead, instead of transmitting data to the gateway and then to a next cluster, the cluster head directly transmits data to next cluster.
U.S. Pat. No. 6,876,643 provides a method for clustering in an ad hoc wireless network. That method organizes a set of nodes into a minimum number of connected clusters of bounded size, defines a master-designate and a slave-designate. The master-designate collects data and the slave-designate is selected as proxy slave to route data. One disadvantage of that method is communication overhead. Instead of transmitting data to the proxy slave and the proxy slave forwarding data to next cluster, the master-designate can directly transmit data to next cluster.
Clustering of devices can also be used for collision minimization and other purposes. Collision causes packet loss. Lost packet needs to be retransmitted. Therefore, packet loss decreases reliability and increases delay. Retransmission increases bandwidth usage and communication overhead, which in turn increases energy consumption, which shortens the life time of battery-powered devices.
To minimize transmission collision in M2M networks, different clustering methods are required. Therefore, it is desirable to provide a clustering method for large scale M2M networks that minimize collisions. Minimizing collisions can improve packet delivery reliability, reduce transmission delay, and increase network throughput.